package 简单.其他;

/**
 * 给你一个下标从 0 开始的整数数组 nums ，该数组的大小为 n ，
 * 请你计算 nums[j] - nums[i] 能求得的 最大差值 ，其中 0 <= i < j < n 且 nums[i] < nums[j] 。
 * <p>
 * 返回 最大差值 。如果不存在满足要求的 i 和 j ，返回 -1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-difference-between-increasing-elements
 */
public class 增量元素之间的最大差值_2016 {

    public static void main(String[] args) {

        int[] nums = {999, 997, 980, 976, 948, 940, 938, 928, 924, 917, 907, 907, 881, 878, 864, 862
                , 859, 857, 848, 840, 824, 824, 824, 805, 802, 798, 788, 777, 775, 766, 755, 748,
                735, 732, 727, 705, 700, 697, 693, 679, 676, 644, 634, 624, 599, 596, 588, 583, 562,
                558, 553, 539, 537, 536, 509, 491, 485, 483, 454, 449, 438, 425, 403, 368, 345,
                327, 287, 285, 270, 263, 255, 248, 235, 234, 224, 221, 201, 189, 187, 183, 179, 168,
                155, 153, 150, 144, 107, 102, 102, 87, 80, 57, 55, 49, 48, 45, 26, 26, 23, 15};
        System.out.println(maximumDifference(nums));

    }

    /**
     * 记录到i之前的最小元素pre，nums[i]-nums[pre]的最大值
     * 注意：必须nums[i] < nums[j]，如果不存在满足要求的 i 和 j ，返回 -1
     *
     * @param nums
     * @return
     */
    public static int maximumDifference(int[] nums) {
        int ans = nums[1] - nums[0];
        int preMin = Math.min(nums[1], nums[0]);
        for (int cur = 2; cur < nums.length; cur++) {
            ans = Math.max(ans, nums[cur] - preMin);
            preMin = Math.min(preMin, nums[cur]);
        }
        return ans <= 0 ? -1 : ans;
    }


    /**
     * 先计算出[0,i]中最小的数字
     */
    public int maximumDifference2(int[] nums) {
        int ans = -1;
        int[] min = new int[nums.length];
        min[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            min[i] = Math.min(min[i - 1], nums[i]);
        }
        for (int j = nums.length - 1; j >= 1; j--) {
            if (nums[j] > min[j - 1]) {
                ans = Math.max(ans, nums[j] - min[j - 1]);
            }
        }

        return ans;
    }

}
